【题解】【化学】实验

原题链接

题意:

nn个液体分组,要求对于任意不同组液体i,ji,jgcsd(ai,aj)x2gcsd(a_i,a_j)\le x^2。求最大的组数,满足组数最大的条件下求每组cic_i的最大值的和。有多组询问,每次给定xx

首先,gcsd\operatorname{gcsd}?那是啥?

按照题目描述里说的,如果定义h(x)h(x)表示x\sqrt x的整数因式部分,那么gcsd(x,y)=h(gcd(x,y))2gcsd(x,y)=h(gcd(x,y))^2

可以看出这玩意也就等于gcd(h(x),h(y))2gcd(h(x),h(y))^2。于是原条件就等价于gcd(h(ai),h(aj))xgcd(h(a_i),h(a_j))\le x,考虑用h(ai)h(a_i)代替原题中的aia_i进行计算

另一个问题是求cic_icic_i定义为bib_i分解成质因数后最大的指数。

h(ai)h(a_i)cic_i都可以用线性筛来求,那么我们的线性筛需要筛四个东西

s[x]s[x]xx的最小质因子

st[x]st[x]xx分解成质因数后s[x]s[x]的指数

sm[x]sm[x]xx分解成质因数后最大的指数

h[x]h[x]x\sqrt x的整数因式部分

std::vector<int> pr;
int s[M], h[M], st[M], sm[M];
void prime() {
	for (int i = 2; i < M; i++) {
		if (!s[i]) { //i是一个质数
			pr.push_back(i);
			s[i] = i;
			st[i] = sm[i] = h[i] = 1;
		}
		for (int j : pr) { //j是i*j的最小质因子
			if (i*j >= M) break;
			s[i*j] = j;
			st[i*j] = (s[i] == j) ? st[i]+1 : 1;
			h[i*j] = (s[i] == j && st[i] & 1) ? h[i]*j : h[i];
			sm[i*j] = std::max(sm[i], st[i*j]);
			if (i % j == 0) break;
		}
	}
}

接下来考虑进一步转化问题。刚才我们说,对于任意不同组液体i,ji,jgcd(h(ai),h(aj))xgcd(h(a_i),h(a_j))\le x

再换句话,如果gcd(h(ai),h(aj))>xgcd(h(a_i),h(a_j))> x,那么i,ji,j必须在同一组

这样的描述可以转化为图论模型:每种液体是一个节点,如果gcd(h(ai),h(aj))>xgcd(h(a_i),h(a_j))> x则节点iijj之间连一条边。很显然一个连通块内的节点必须在同一组,既然我们要组数最大,那么每个连通块是一组就是最优方案。最大的组数也就是连通块个数,实验得分也很好求,找到每个连通块内最大的cic_i然后加起来。

举个例子,当x=2x=2的时候样例大概长这样(点上的数字就是aia_i

于是我们就有了最暴力的算法:对于每个xxO(n2)O(n^2)暴力建图,dfs找连通块,时间复杂度O(mn2)O(mn^2)。打上这个应该就可以拿30分。

不过,我们发现,这张图里很多点实际都是没有用的。所有h(ai)xh(a_i)\le x的点就是没有用的,它们都没有连边,都可以单独一组直接计入答案。可以预处理出每个xxh(ai)xh(a_i)\le x的点对答案的贡献,这样建图的时候就不用考虑这些点了。

另一方面,对于h(ai)>xh(a_i)>x的点,如果有很多个点的h(ai)h(a_i)相等,那么这些点都必须在同一组,其中cic_i最大的那个可能计入贡献。不妨把它们当作一个点,这个点的cic_i就是原来那些点cic_i的最大值。

可以考虑按照h(ai)h(a_i)把所有点分类,由于h(ai)sqrt(ai)200h(a_i)\le sqrt(a_i)\le 200,那么最多也就只有200200类,也就是图上最多有200200个点。而且枚举xx也只需要枚举到max{h(ai)}max\{h(a_i)\},这个时候建图应该可以AC此题了。代码就不放了。

但是这样复杂度是O(a32)O(a^\frac{3}{2}),并不是最优复杂度,如果aa的范围是2×1072\times 10^7就没了。

可以考虑从max{h(ai)}max\{h(a_i)\}开始,从大到小枚举xx。这样相当于在图上不断加边,连通块可以用并查集维护。具体实现可以在计算完xx的答案之后,把所有xx的倍数合并起来。时间复杂度O(alog2a)O(\sqrt alog^2a),低于线性复杂度,所以实际上复杂度的瓶颈是线性筛,总体复杂度应该是O(n+m+max{ai}+max{bi})O(n+m+max\{a_i\}+max\{b_i\})

完整代码

#include <cstdio>
#include <vector>
#define N 200000
#define M 20000001
#define R 201
#define L 40001
std::vector<int> pr;
int s[M], h[L]; char st[M], sm[M]; //int改成char极限卡内存
void prime() {
	for (int i = 2; i < M; i++) {
		if (!s[i]) {
			pr.push_back(i);
			s[i] = i;
			st[i] = sm[i] = 1;
			if (i < L) h[i] = 1;
		}
		for (int j : pr) {
			if (i*j >= M) break;
			s[i*j] = j;
			st[i*j] = (s[i] == j) ? st[i]+1 : 1;
			if (i*j < L) h[i*j] = (s[i] == j && st[i] & 1) ? h[i]*j : h[i];
			sm[i*j] = std::max(sm[i], st[i*j]);
			if (i % j == 0) break;
		}
	}
}
struct pair {int x, y; };
pair operator + (pair a, pair b) {
	return (pair) {a.x + b.x, a.y + b.y};
}
int n, m, a[N], b[N], mv[R], f[R], p[R];
pair co[R], ans[R], cnt;
int fa(int x) {
	return x == f[x] ? x : f[x] = fa(f[x]);
}
int main() {
	prime();
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", a+i);
	for (int i = 0; i < n; i++) {
		scanf("%d", b+i);
		a[i] = h[a[i]];
		b[i] = sm[b[i]];
		co[a[i]] = co[a[i]] + (pair) {1, b[i]};
		mv[a[i]] = std::max(mv[a[i]], b[i]);
	}
	for (int i = 2; i < R; i++)
		co[i] = co[i] + co[i-1];
	for (int i = R-1; i >= 2; i--) {
		ans[i] = co[i]+cnt;
		if (!mv[i]) continue;
		f[i] = i; p[i] = mv[i];
		cnt = cnt + (pair) {1, mv[i]};
		for (int j = 2; i*j < R; j++) if (mv[i*j]) {
			int x = fa(i), y = fa(i*j);
			if (x != y) {
				f[x] = y;
				cnt.x--;
				cnt.y -= std::min(p[x], p[y]);
				p[y] = std::max(p[x], p[y]);
			}
		}
	}
	while (m--) {
		int x; scanf("%d", &x);
		pair p = (x < R) ? ans[x] : co[R-1];
		printf("%d %d\n", p.x, p.y);
	}
}